package main.leetcode.clockin.May;

import main.datastruc.TreeNode;

/**
 * 105.从前序与中序遍历序列构造二叉树
 *
 * <p>根据一棵树的前序遍历与中序遍历构造二叉树。
 *
 * <p>注意: 你可以假设树中没有重复的元素。
 */
public class day22 {
    public static void main(String[] args) {
        System.out.println(
                new day22().buildTree(new int[] {3, 9, 20, 15, 7}, new int[] {9, 3, 15, 20, 7}));
    }

    public TreeNode buildTree(int[] preorder, int[] inorder) {
        int n = preorder.length;
        return n < 1 ? null : buildTree(preorder, 0, n - 1, inorder, 0, n - 1);
    }

    private TreeNode buildTree(int[] preorder, int s1, int e1, int[] inorder, int s2, int e2) {
        if (s1 > e1 || s2 > e2) {
            return null;
        }
        TreeNode root = new TreeNode(preorder[s1]);
        int et = s2;
        while (et < e2 && inorder[et] != preorder[s1]) {
            ++et;
        }
        root.left = buildTree(preorder, s1 + 1, s1 + et - s2, inorder, s2, et);
        root.right = buildTree(preorder, s1 + et - s2 + 1, e1, inorder, et + 1, e2);
        return root;
    }
}
